import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/5 15:23
 * @description
 */
public class Solution {
    public static void main(String[] args) {

    }
    class RLEIterator {
        int[] nums;
        /**
         * i 为当前元素下标，q为元素已经删除的次数
         */
        int i, q;
        public RLEIterator(int[] encoding) {
            nums = encoding;
            i = q = 0;
        }

        public int next(int n) {
            while (i < nums.length) {
                // 当前元素删除的次数 + 再次删除的次数 > 总拥有的次数
                if (q + n > nums[i]) {
                    n -= nums[i] - q;
                    q = 0;
                    i += 2;
                }else {
                    q += n;
                    return nums[i + 1];
                }
            }
            return -1;
        }
    }
}
class RLEIterator {
    TreeMap<Long, Integer> map;
    long cur;
    public RLEIterator(int[] encoding) {
        map = new TreeMap<>();
        cur = 0;
        long cnt = 0;
        for (int i = 0; i < encoding.length; i += 2) {
            if (encoding[i] == 0) {
                continue;
            }
            cnt += encoding[i];
            map.put(cnt, encoding[i + 1]);
        }
    }

    public int next(int n) {
        cur += n;
        // 二分查找 好慢
        Long key = map.ceilingKey(cur);
        if (key == null) {
            return -1;
        }
        return map.get(key);
    }
}